#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class Solution
{
public:
    vector<int> ans;
    stack<int> stk;
    stack<int> frontier;
    vector<int> eventualSafeNodes(vector<vector<int>> &graph)
    {
        if (graph.size() == 0)
            return {};
        vector<bool> visited(graph.size(), false);
        vector<int> start(graph.size(), 0);
        vector<int> finish(graph.size(), INT32_MAX);
        int timeNow = 0;
        for (int i = 0; i < graph.size(); ++i) //dfs
        {
            if (visited[i] == true)
                continue;
            frontier.emplace(i);
            while (frontier.empty() == false)
            {
                int node = frontier.top();
                frontier.pop();
                if (visited[node] == true)
                    continue;
                visited[node] = true;
                stk.push(node);
                for (int j = 0; j < graph[node].size(); ++j)
                {
                    frontier.emplace(graph[node][j]);
                }
            }
        }
        //transpose
        vector<vector<int>> tg(graph.size());
        for (int i = 0; i < graph.size(); ++i)
        {
            for (int j = 0; j < graph[i].size(); ++j)
            {
                tg[graph[i][j]].push_back(i);
            }
        }
        // 输出只有一个节点的连通片
        //TODO :重写这一块，用strat,finish区分节点访问状态来划分强联通区域
        visited.assign(visited.size(), false);
        while (stk.empty() == false)
        {
            int i = stk.top(), cnt1 = 0, cnt2 = 0;
            stk.pop();
            if (visited[i] == true)
                continue;
            frontier.push(i);
            while (frontier.empty() == false)
            {
                int node = frontier.top();
                frontier.pop();
                cnt2++;
                if (visited[node] == true)
                    continue;
                cnt1++;
                visited[node] = true;
                for (int j = 0; j < tg[node].size(); ++j)
                {
                    frontier.push(tg[node][j]);
                }
            }
            if (cnt1 <= cnt2)
                ans.push_back(i);
        }
        sort(ans.begin(), ans.end());
        return ans;
    }
};
int main()
{
    vector<vector<int>> graph = {
        {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}}};
    return 0;
}